The present invention relates to a method for optimizing the placement of components in designing a semiconductor device.
A simulated annealing (SA) method, one of combinatorial optimization methods, was proposed by S. Kirkpatrick et al. in "Optimization by Simulated Annealing", SCIENCE, Vol. 220, No. 4598, pp. 671-680, May 1983. The SA method is used for carrying out a combinatorial optimization by adopting a Monte-Carlo (MC) method, which is a computer simulation method in thermodynamics. In accordance with the SA method, a temperature and an energy value defined in thermodynamics are respectively replaced with an effective temperature as a parameter and the value of an estimate (i.e., a cost value) used for estimating a placement produced in a combinatorial problem. Specifically, first, a cost value is obtained by exchanging the positions of two components selected from a placement produced at an effective temperature T. And then it is determined in accordance with the MC method using the cost value whether or not the exchange is allowable. If it has been determined that the exchange is not allowable, then the two components are returned to their original positions and another pair of components are newly selected from the placement. Alternatively, if it has been determined that the exchange is allowable, then another pair of components are newly selected from the modified placement reflecting the exchange, and the positions of the two components selected are exchanged with each other, thereby obtaining a cost value. This determination is carried out N times, which is a predetermined number of times the placement should be improved, thereby optimizing the component placement at the effective temperature T. In accordance with the SA method, the component placement is optimized at an effective temperature (high temperature) Ts, which is slowly lowered by a predetermined temperature every time. At every effective temperature lowered, the optimized placement is further optimized. By repeatedly performing this procedure, the temperature is slowly cooled down to an effective temperature (low temperature) Te. And a near-optimal solution can be found by regarding the placement at the effective temperature (low temperature) Te as an optimal solution.
FIGS. 4A through 4C are diagrams illustrating a process for optimizing the placement of components (e.g., standard cells) by applying the SA method to a placement model so as to optimize a cost value (i.e., a total wire length). In this placement model, each component is bonded to four surrounding components (i.e., a four-direction bonding is implemented). A component located in the central 4.times.4 grid (where number Ne of components=16) is a component E to be placed, while a peripheral component Er is a fixed component. The distance between adjacent components is a unit distance of 1. The combinatorial problem is a problem of obtaining an optimum placement from an initial placement in which components are placed at random as shown in FIG. 4A. In accordance with the SA method, an optimum placement shown in FIG. 4C is obtained from the initial placement shown in FIG. 4A via an intermediate placement shown in FIG. 4B by slowing lowering the effective temperature T.
Next, it will be described with reference to FIG. 5 how the cost value changes according to the SA method. FIG. 5 is a graph illustrating a relationship between an effective temperature T and a cost value where the number Ne of components is 25 (=5.times.5). The effective temperature T and the cost value are both represented by relative scales. While the effective temperature T is in the range from 10.0 to 4.0, the cost value repeatedly increases and decreases to a large degree. By contrast, while the effective temperature T is in the range from 4.0 to 1.0, the cost value still repeatedly increases and decreases, but generally tends to decrease as the effective temperature T decreases. A quantity obtained by differentiating a cost value by an effective temperature T is a quantity corresponding to specific heat. In FIG. 5, Tc is a temperature, at which the specific heat reaches a peak, and can be found as a result of the slow cooling employed in the SA method.
FIG. 6 is a table showing specific examples of the results obtained by a conventional pair-wise exchange (PW) method and the SA method. The pair-wise exchange method optimizes a placement by allowing components to be exchanged only when a cost value decreases. According to the SA method, each cost value, i.e., the total wire length, can be about a half to about a third of the counterpart obtained by the PW method. Therefore, a better solution (i.e., a better component placement) can be attained.
However, in accordance with the SA method, as the number of components increases, an iterative number of optimization processes drastically increases. As shown in FIG. 6, if the number Ne of components increases from 25 (=5.times.5) to 64 (=8.times.8) substantially threefold, the iterative number of optimization processes increases about elevenfold. And if the number Ne of components increases from 64 (=8.times.8) to 100 (=10.times.10) substantially twofold, the iterative number of optimization processes increases about ninefold. Accordingly, if one million or more transistors are to be placed in accordance with the SA method, then the process should be performed an enormous number of times. Thus, it is impossible to complete the process within a practical time.